package internal.selection;

/**
 * @描述：每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可
 * @作者：hongxingfan
 * @时间：2014年9月5日 上午9:05:17
 */
public class BinarySelectionSort {

    public static void main(String[] args) {
        int[] datas = { 9, 4, 1, 8, 7, 5, 2, 0, 3, 4, 6 };

        binarySelectiontSort(datas);

        for (int data : datas)
            System.out.print(data + " ");
        System.out.println();
    }

    // 如果要用选择选择排序，使用二元选择排序
    public static void binarySelectiontSort(int[] datas) {
        int length = datas.length - 1;
        // 比简单选择排序减少一半的循环
        for (int i = 0; i < length / 2; i++) {
            int min = datas[i];
            int max = datas[i];
            int minIndex = i;
            int maxIndex = i;
            // 每次遍历选出最大和最小2个
            for (int j = i + 1; j < length - i; j++) {
                if (min > datas[j]) {
                    min = datas[j];
                    minIndex = j;
                }
                if (max < datas[j]) {
                    max = datas[j];
                    maxIndex = j;
                }
            }
            // 先换最大的
            datas[maxIndex] = datas[length - i];
            datas[length - i] = max;
            // 再换最小的
            datas[minIndex] = datas[i];
            datas[i] = min;
        }
    }
}
